Binary prefix divisible by 5

Time: O(N); Space: O(1); easy

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: A = [0, 1, 1]

Output: [True, False, False]

Explanation:

  • The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.

  • Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: A = [1, 1, 1]

Output: [False, False, False]

Example 3:

Input: A = [0, 1, 1, 1, 1, 1]

Output: [True, False, False, False, True, False]

Example 4:

Input: A = [1, 1, 1, 0, 1]

Output: [False, False, False, False, False]

Notes:

  • 1 <= len(A) <= 30000

  • A[i] is 0 or 1

[4]:

class Solution1(object):
    def prefixesDivBy5(self, A):
        """
        :type A: List[int]
        :rtype: List[bool]
        """
        for i in range(1, len(A)):
            A[i] += A[i-1] * 2 % 5
        return [x % 5 == 0 for x in A]

[5]:

s = Solution1()
A = [0, 1, 1]
assert s.prefixesDivBy5(A) == [True, False, False]
A = [1, 1, 1]
assert s.prefixesDivBy5(A) == [False, False, False]
A = [0, 1, 1, 1, 1, 1]
assert s.prefixesDivBy5(A) == [True, False, False, False, True, False]
A = [1, 1, 1, 0, 1]
assert s.prefixesDivBy5(A) == [False, False, False, False, False]